class Solution {
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    int m = 0, n = 0;
 
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        vector<vector<bool>> vis1(m, vector<bool>(n, false));
        vector<vector<bool>> vis2(m, vector<bool>(n, false));
        for(int i = 0; i < n; ++i) // 遍历周围
        {
            dfs(heights, 0, i, vis1); // 太平洋
            dfs(heights, m - 1, i, vis2); // 大西洋
        }
        for(int i = 0; i < m; ++i)
        {
            dfs(heights, i, 0, vis1); // 太平洋
            dfs(heights, i, n - 1, vis2); // 大西洋
        }
        vector<vector<int>> ret;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(vis1[i][j] && vis2[i][j])
                    ret.push_back({i, j});
            }
        }
        return ret;
    }
 
    void dfs(vector<vector<int>>& heights, int sr, int sc, vector<vector<bool>>& vis)
    {
        vis[sr][sc] = true;
        for(int i = 0; i < 4; ++i)
        {
            int x = sr + dx[i], y = sc + dy[i];
            if(x >= 0 && x < m && y >= 0 && y < n  && !vis[x][y] && heights[x][y] >= heights[sr][sc])
            {
                dfs(heights, x, y, vis);
            }
        }
    }
};